#include "puzzlestate.h"
#include <algorithm>
#include <random>
#include <chrono>
#include <sstream>
#include <cmath>

PuzzleState::PuzzleState(int size) : size(size)
{
    state.resize(size * size);
    for (int i = 0; i < size * size; ++i) {
        state[i] = i;
    }
}

PuzzleState::PuzzleState(const std::vector<int>& state, int size) 
    : state(state), size(size)
{
}

PuzzleState::PuzzleState(const std::vector<std::vector<int>>& state2d)
{
    size = static_cast<int>(state2d.size());
    state.resize(size * size);
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            state[i * size + j] = state2d[i][j];
        }
    }
}

PuzzleState::PuzzleState(const PuzzleState& other) 
    : state(other.state), size(other.size)
{
}

bool PuzzleState::operator==(const PuzzleState& other) const
{
    return state == other.state && size == other.size;
}

bool PuzzleState::operator!=(const PuzzleState& other) const
{
    return !(*this == other);
}

bool PuzzleState::operator<(const PuzzleState& other) const
{
    if (size != other.size) {
        return size < other.size;
    }
    return state < other.state;
}

PuzzleState& PuzzleState::operator=(const PuzzleState& other)
{
    if (this != &other) {
        state = other.state;
        size = other.size;
    }
    return *this;
}

std::vector<PuzzleState> PuzzleState::getSuccessors() const
{
    std::vector<PuzzleState> successors;
    
    for (int direction = 0; direction < 4; ++direction) {
        if (canMove(direction)) {
            successors.push_back(move(direction));
        }
    }
    
    return successors;
}

bool PuzzleState::canMove(int direction) const
{
    QPoint blankPos = getBlankPosition();
    int row = blankPos.y();
    int col = blankPos.x();
    
    switch (direction) {
        case 0: return row > 0;           // 上
        case 1: return row < size - 1;    // 下
        case 2: return col > 0;           // 左
        case 3: return col < size - 1;    // 右
        default: return false;
    }
}

PuzzleState PuzzleState::move(int direction) const
{
    if (!canMove(direction)) {
        return *this;
    }
    
    QPoint blankPos = getBlankPosition();
    int blankRow = blankPos.y();
    int blankCol = blankPos.x();
    int blankIndex = blankRow * size + blankCol;
    
    int newRow = blankRow;
    int newCol = blankCol;
    
    switch (direction) {
        case 0: newRow--; break; // 上
        case 1: newRow++; break; // 下
        case 2: newCol--; break; // 左
        case 3: newCol++; break; // 右
    }
    
    int newIndex = newRow * size + newCol;
    
    PuzzleState newState(*this);
    std::swap(newState.state[blankIndex], newState.state[newIndex]);
    
    return newState;
}

QPoint PuzzleState::getBlankPosition() const
{
    for (int i = 0; i < state.size(); ++i) {
        if (state[i] == 0) {
            return QPoint(i % size, i / size);
        }
    }
    return QPoint(-1, -1);
}





//A*算法-曼哈顿距离
int PuzzleState::manhattanDistance(const PuzzleState& goal) const
{
    int distance = 0;
    
    for (int i = 0; i < state.size(); ++i) {
        if (state[i] != 0) {
            // 找到目标位置
            int targetPos = -1;
            for (int j = 0; j < goal.state.size(); ++j) {
                if (goal.state[j] == state[i]) {
                    targetPos = j;
                    break;
                }
            }
            
            if (targetPos != -1) {
                int currentRow = i / size;
                int currentCol = i % size;
                int targetRow = targetPos / size;
                int targetCol = targetPos % size;
                
                distance += std::abs(currentRow - targetRow) + std::abs(currentCol - targetCol);
            }
        }
    }
    
    return distance;
}





//A*算法-不在位数码数
int PuzzleState::misplacedTiles(const PuzzleState& goal) const
{
    int count = 0;
    
    for (int i = 0; i < state.size(); ++i) {
        if (state[i] != 0 && state[i] != goal.state[i]) {
            count++;
        }
    }
    return count;
}






bool PuzzleState::isSolvable(const PuzzleState& goal) const
{
    int inversions = getInversions();
    
    if (size % 2 == 1) {
        // 奇数大小：逆序数为偶数时可解
        return inversions % 2 == 0;
    } else {
        // 偶数大小：需要考虑空格位置
        int blankRow = findBlankRow();
        if ((size - blankRow) % 2 == 1) {
            return inversions % 2 == 0;
        } else {
            return inversions % 2 == 1;
        }
    }
}

std::string PuzzleState::toString() const
{
    std::stringstream ss;
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            int value = state[i * size + j];
            if (value == 0) {
                ss << "  ";
            } else {
                ss << value << " ";
            }
        }
        if (i < size - 1) ss << "\n";
    }
    return ss.str();
}

std::vector<std::vector<int>> PuzzleState::getGrid() const
{
    std::vector<std::vector<int>> grid(size, std::vector<int>(size));
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            grid[i][j] = state[i * size + j];
        }
    }
    return grid;
}

void PuzzleState::setState(const std::vector<int>& newState)
{
    if (newState.size() == size * size) {
        state = newState;
    }
}

int PuzzleState::getValue(int row, int col) const
{
    if (row < 0 || row >= size || col < 0 || col >= size) {
        return -1; // 无效位置
    }
    return state[row * size + col];
}

void PuzzleState::setValue(int row, int col, int value)
{
    if (row >= 0 && row < size && col >= 0 && col < size) {
        state[row * size + col] = value;
    }
}

PuzzleState PuzzleState::getDefaultInitial(int size)
{
    std::vector<int> initial;
    if (size == 3) {
        initial = {1, 2, 3, 8, 0, 4, 7, 6, 5};
    } else if (size == 4) {
        initial = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0, 15};
    } else {
        // 默认生成一个简单的初始状态
        initial.resize(size * size);
        for (int i = 0; i < size * size - 1; ++i) {
            initial[i] = i + 1;
        }
        initial[size * size - 1] = 0;
        // 简单打乱
        if (size * size > 2) {
            std::swap(initial[0], initial[1]);
        }
    }
    
    return PuzzleState(initial, size);
}

PuzzleState PuzzleState::getDefaultGoal(int size)
{
    std::vector<int> goal(size * size);
    for (int i = 0; i < size * size - 1; ++i) {
        goal[i] = i + 1;
    }
    goal[size * size - 1] = 0;
    
    return PuzzleState(goal, size);
}

PuzzleState PuzzleState::generateRandom(int size)
{
    std::vector<int> state(size * size);
    for (int i = 0; i < size * size; ++i) {
        state[i] = i;
    }
    
    // 使用当前时间作为随机种子
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::shuffle(state.begin(), state.end(), std::default_random_engine(seed));
    
    PuzzleState randomState(state, size);
    PuzzleState goal = getDefaultGoal(size);
    
    // 确保生成的状态是可解的
    if (!randomState.isSolvable(goal)) {
        // 如果不可解，交换前两个非零元素
        for (int i = 0; i < state.size() - 1; ++i) {
            if (state[i] != 0 && state[i + 1] != 0) {
                std::swap(state[i], state[i + 1]);
                break;
            }
        }
        randomState.setState(state);
    }
    
    return randomState;
}

// UI中使用的别名方法
PuzzleState PuzzleState::getDefaultInitialState(int size)
{
    return getDefaultInitial(size);
}

PuzzleState PuzzleState::getDefaultGoalState(int size)
{
    return getDefaultGoal(size);
}

PuzzleState PuzzleState::generateRandomSolvableState(int size)
{
    return generateRandom(size);
}

int PuzzleState::getInversions() const
{
    int inversions = 0;
    std::vector<int> nonZeroElements;
    
    for (int value : state) {
        if (value != 0) {
            nonZeroElements.push_back(value);
        }
    }
    
    for (int i = 0; i < nonZeroElements.size(); ++i) {
        for (int j = i + 1; j < nonZeroElements.size(); ++j) {
            if (nonZeroElements[i] > nonZeroElements[j]) {
                inversions++;
            }
        }
    }
    
    return inversions;
}

int PuzzleState::findBlankRow() const
{
    QPoint blankPos = getBlankPosition();
    return blankPos.y();
}

int PuzzleState::getInversionsCount() const
{
    return getInversions();
}